#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <map>
using namespace std;
class Solution {
public:
    string addBinary(string a, string b) {
        int n1 = a.size();
        int n2 = b.size();
        int c = 0;
        int i = 1;
        int t1, t2;
        char tc;
        string ans = "";
        for (; i <= n1 || i <= n2; i++)
        {
            t1 = n1 >= i ? a[n1 - i] - '0' : 0;
            t2 = n2 >= i ? b[n2 - i] - '0' : 0;
            tc = '0' + (t1 + t2 + c) % 2;
            c = (t1 + t2 + c) / 2;
            ans.push_back(tc);
        }
        if (c)ans.push_back('1');
        reverse(ans.begin(), ans.end());
        if (!ans.size())ans.push_back('0');
        return ans;
    }
};